/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 16
 * Time: 21:44
 */
//牛客 兑换零钱(一)
public class Solution7 {
    public int minMoney (int[] arr, int aim) {
        int n = arr.length, INF = 0x3f3f3f3f;
        //dp[i][j]表示从前i个硬币中挑选硬币，使硬币总和正好等于j，在这所有的选法中，最少的硬币个数
        int[][] dp = new int[n + 1][aim + 1];
        for (int j = 1; j <= aim; j++) dp[0][j] = INF;
        for (int i = 1; i <= n ; i++) {
            for (int j = 0; j <= aim; j++) {
                dp[i][j] = dp[i - 1][j];//这行代码不能写在下面的if语句里面
                if(j >= arr[i - 1]) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - arr[i - 1]] + 1);//完全背包问题用dp[i][j-arr[i-1]]+1
                }
            }
        }
        return dp[n][aim] == INF ? -1 : dp[n][aim];
    }

    //对上面的代码进行空间优化
    public int minMoney1 (int[] arr, int aim) {
        int n = arr.length, INF = 0x3f3f3f3f;
        //dp[i][j]表示从前i个硬币中挑选硬币，使硬币总和正好等于j，在这所有的选法中，最少的硬币个数
        int[] dp = new int[aim + 1];
        for (int i = 1; i <= aim; i++) dp[i] = INF;
        for (int i = 1; i <= n ; i++) {//完全背包问题空间优化时数组从左到右赋值(01背包问题则从右到左赋值)
            for (int j = arr[i - 1]; j <= aim; j++) {
                    dp[j] = Math.min(dp[j], dp[j - arr[i - 1]] + 1);//完全背包问题用dp[i][j-arr[i-1]]+1
            }
        }
        return dp[aim] == INF ? -1 : dp[aim];
    }
}
